UVa/563 - Crimewave/563.cpp

   1 using namespace std;
   2 #include <algorithm>
   3 #include <iostream>
   4 #include <iterator>
   5 #include <sstream>
   6 #include <fstream>
   7 #include <cassert>
   8 #include <climits>
   9 #include <cstdlib>
  10 #include <cstring>
  11 #include <string>
  12 #include <cstdio>
  13 #include <vector>
  14 #include <cmath>
  15 #include <queue>
  16 #include <deque>
  17 #include <stack>
  18 #include <map>
  19 #include <set>
  20
  21 #define foreach(x, v) for (typeof (v).begin() x = (v).begin(); x != (v).end(); ++x)
  22 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  23 #define D(x) cout << #x " is " << x << endl
  24
  25 /*
  26   Maximum number of edges is around 55*55*2*6*2.  There are less than
  27   55*55 nodes. We split each node in two (in and out) hence
  28   55*55*2. We assume each node is connected to 6 neighbors: 4 partners
  29   in the grid plus the source and sink, hence 55*55*2*6. But for each
  30   edge there are actually two edges (counting its complementary for
  31   the backflow).  This is actually and upper bound because I'm too
  32   lazy to find out the exact number of edges.
  33 */
  34 const int MAXE = 55*55*2*6*2;
  35
  36 int cap[MAXE];
  37 int first[MAXE];
  38 int next[MAXE];
  39 int adj[MAXE];
  40 int current_edge;
  41 int rows, cols;
  42
  43
  44 const int oo = INT_MAX / 2 - 1;
  45
  46 int add_edge(int u, int v, int c){
  47   adj[current_edge] = v;
  48   cap[current_edge] = c;
  49   next[current_edge] = first[u];
  50   first[u] = current_edge;
  51   current_edge++;
  52
  53   adj[current_edge] = u;
  54   cap[current_edge] = 0;
  55   next[current_edge] = first[v];
  56   first[v] = current_edge;
  57   current_edge++;
  58 }
  59
  60 inline int in(int u){ return 2*u; }
  61 inline int out(int u){ return 2*u + 1; }
  62 inline int number(int r, int c){ return r * cols + c; }
  63
  64 void print_edges(int u){
  65   printf("Edges going out from %d:\n", u);
  66   for (int e = first[u]; e != -1; e = next[e]){
  67     printf("(v = %d, cap = %d)\n", adj[e], cap[e]);
  68   }
  69 }
  70
  71 int q[MAXE];
  72 int incr[MAXE];
  73 int arrived_by[MAXE]; //arrived_by[i] = The last edge that I used to reach node i
  74 int find_augmenting_path(int src, int snk){
  75   /*
  76     Make a BFS to find an augmenting path from the source to the sink.
  77     Then pump flow through this path, and return the amount that was pumped.
  78   */
  79   memset(arrived_by, -1, sizeof arrived_by);
  80   int h = 0, t = 0;
  81   q[t++] = src;
  82   arrived_by[src] = -2;
  83   incr[src] = oo;
  84   while (h < t && arrived_by[snk] == -1){ //BFS
  85     int u = q[h++];
  86     for (int e = first[u]; e != -1; e = next[e]){
  87       int v = adj[e];
  88       if (arrived_by[v] == -1 && cap[e] > 0){
  89         arrived_by[v] = e;
  90         incr[v] = min(incr[u], cap[e]);
  91         q[t++] = v;
  92       }
  93     }
  94   }
  95
  96   if (arrived_by[snk] == -1) return 0;
  97
  98   int cur = snk;
  99   int neck = incr[snk];
 100   while (cur != src){
 101     //Remove capacity from the edge used to reach node "cur"
 102     //Add capacity to the backedge
 103     cap[arrived_by[cur]] -= neck;
 104     cap[arrived_by[cur] ^ 1] += neck;
 105
 106     cur = adj[arrived_by[cur] ^ 1]; //move backwards in the path
 107   }
 108   return neck;
 109 }
 110
 111 int max_flow(int src, int snk){
 112   int ans = 0, neck;
 113   while ((neck = find_augmenting_path(src, snk)) != 0){
 114     ans += neck;
 115   }
 116   return ans;
 117 }
 118
 119
 120 int main(){
 121   int cases;
 122   for(scanf("%d", &cases); cases--; ){
 123     int banks;
 124     if (scanf("%d %d %d", &rows, &cols, &banks) != 3) break;
 125
 126     int source = rows * cols, sink = source + 1;
 127     current_edge = 0;
 128     memset(next, -1, sizeof next);
 129     memset(first, -1, sizeof first);
 130
 131     for (int k=0; k<banks; ++k){
 132       int r, c;
 133       scanf("%d %d", &r, &c);
 134       r--, c--;
 135       add_edge(out(number(r, c)), in(sink), 1);
 136     }
 137
 138     for (int i=0; i<rows; ++i){
 139       for (int j=0; j<cols; ++j){
 140         if (i == 0 || i == rows - 1 || j == 0 || j == cols - 1){ //node lies on the border
 141           add_edge(out(source), in(number(i, j)), 1);
 142         }
 143         if (i - 1 >= 0){
 144           add_edge(out(number(i, j)), in(number(i-1, j)), 1);
 145         }
 146         if (i + 1 < rows){
 147           add_edge(out(number(i, j)), in(number(i+1, j)), 1);
 148         }
 149         if (j - 1 >= 0){
 150           add_edge(out(number(i, j)), in(number(i, j-1)), 1);
 151         }
 152         if (j + 1 < cols){
 153           add_edge(out(number(i, j)), in(number(i, j+1)), 1);
 154         }
 155       }
 156     }
 157
 158     for (int i=0; i<rows; ++i){
 159       for (int j=0; j<cols; ++j){
 160         add_edge(in(number(i, j)), out(number(i, j)), 1);
 161       }
 162     }
 163     add_edge(in(source), out(source), oo);
 164     add_edge(in(sink), out(sink), oo);
 165
 166     /*
 167     printf("in nodes:\n");
 168     for (int i=0; i<rows; ++i){
 169       for (int j=0; j<cols; ++j){
 170         print_edges(in(number(i, j)));
 171       }
 172     }
 173     printf("out nodes:\n");
 174     for (int i=0; i<rows; ++i){
 175       for (int j=0; j<cols; ++j){
 176         print_edges(out(number(i, j)));
 177       }
 178     }
 179
 180     print_edges(in(source));
 181     print_edges(out(source));
 182
 183     print_edges(in(sink));
 184     print_edges(out(sink));
 185     */
 186
 187     int f = max_flow(in(source), out(sink));
 188
 189     printf("%s\n", f == banks ? "possible" : "not possible");
 190   }
 191   return 0;
 192 }